ASN.1 X.680 Компілятор Сохацького

У статті представлений повний Swift "ASN.1 компілятор" на мові Elixir.
Автор — Максим Сохацький, 2023-9-1.

$ ./asn1.ex Copyright © 2023 Namdak Tonpa. ISO 8824 ITU/IETF X.680-690 ERP/1 ASN.1 DER Compiler, version 0.9.1. Usage: ./asn1.ex help | compile [-v] [input [output]]

Зміст

1) Техніка компіляції та розміточний парсер
2) Послідовності та множини
3) Імплісити, експлісити та опшинали
4) Рекурсивні суми
5) Переліки та цілочисельні переліки
6) Тензори

Техніка компіляції

Оскільки мова ASN.1 має чіткий синтаксис побудова її компілятора може базуватися на BNF парсер генераторах таких як lexx/yacc або їх аналонах на інших мовах програмування leex/yexx (Erlang), Citron (Swift), ANTLR (Java). Загалом нас цікавитимуть LL, LR, LALR, SLR. Але найшвидші парсери це потокові бінарні, Erlang-овий саме такий і займає 2000 рядків разом з токенайзером на 100 рядків.

Технічно, ASN.1 компілятори є AST транформаціями з вихідної мови в цільову, в даному випадку з Erlang шляхом Elixir в Swift. Основне завдання при цьому побудувати базовий розміточний парсер у вигляді мікро-бібліотеки, яку буде використовувати як хелпери згенерований код. В нашому випадку такою бібліотекою є swift-asn1 від Apple тому це теж нам полегшує завдання. Таким чином наш згенерований код сумісний з усіма екстеншинами з бібліотек Apple.

Розміточний парсер

В нас в ЗОШ №5 вчився математик Сергій Книш, який закінчив МГУ в 19 і поїхав викладати в Каліфорнію. Я коли був в Сан-Франціско заходив до нього в гості і він розказува таку байку, а він на байки багатий бо він писав мережевий протокол IPX для шкільного комплексу Корветів і БК-0010 шоб можна було в іграшки по мережі гратися і міг в памʼяті сумувати ряди з точністю до всіх розрядів калькулятора. Так от він розказував шо коли ше тільки починався С++, то таблицю віртуальних методів використовували як масив який індексувався байткодом операції, і коли ви читали байт зі стріма ви простоо викликали функцію з цим індексом в таблиці віртуальнихх методів для десеріалізації цього типу даних. Хоча це байка але в ній є зерно істини, розрізати десеріалізатор і серіалізатор на примітивні функції, кожна з яких займається своїм байт-кодом — техніка, що притаманна багатьом бібліотечним парсерам на мовах програмування C++, Rust, Swift, Java, тощо. Приблизно така сама архітектура і у розміточного TLV парсера Apple.

Послідовності та множини

Простий приклад з якого варто почати імплементацію будь якого ASN.1 компілятора.

U ::= SEQUENCE { a SET OF INTEGER (0..7), b SET OF INTEGER (0..7), c INTEGER (0..7), d INTEGER (0..7), e BOOLEAN, f BOOLEAN, g SET OF INTEGER (0..7) OPTIONAL, h INTEGER (0..7), i INTEGER (0..7), j OCTET STRING OPTIONAL, k BOOLEAN OPTIONAL }
@usableFromInline struct U: DERImplicitlyTaggable, Hashable, Sendable { @inlinable static var defaultIdentifier: ASN1Identifier { .sequence } @usableFromInline var a: [ArraySlice<UInt8>] @usableFromInline var b: [ArraySlice<UInt8>] @usableFromInline var c: ArraySlice<UInt8> @usableFromInline var d: ArraySlice<UInt8> @usableFromInline var e: Bool @usableFromInline var f: Bool @usableFromInline var g: [ArraySlice<UInt8>]? @usableFromInline var h: ArraySlice<UInt8> @usableFromInline var i: ArraySlice<UInt8> @usableFromInline var j: ASN1OctetString? @usableFromInline var k: Bool? @inlinable init(a: [ArraySlice<UInt8>], b: [ArraySlice<UInt8>], c: ArraySlice<UInt8>, d: ArraySlice<UInt8>, e: Bool, f: Bool, g: [ArraySlice<UInt8>]?, h: ArraySlice<UInt8>, i: ArraySlice<UInt8>, j: ASN1OctetString?, k: Bool?) { self.a = a ; self.b = b ; self.c = c ; self.d = d ; self.e = e ; self.f = f ; self.g = g ; self.h = h ; self.i = i ; self.j = j ; self.k = k } @inlinable init(derEncoded root: ASN1Node, withIdentifier identifier: ASN1Identifier) throws { self = try DER.sequence(root, identifier: identifier) { nodes in let a: [ArraySlice<UInt8>] = try DER.set(of: ArraySlice<UInt8>.self, identifier: .set, nodes: &nodes) let b: [ArraySlice<UInt8>] = try DER.set(of: ArraySlice<UInt8>.self, identifier: .set, nodes: &nodes) let c: ArraySlice<UInt8> = try ArraySlice<UInt8>(derEncoded: &nodes) let d: ArraySlice<UInt8> = try ArraySlice<UInt8>(derEncoded: &nodes) let e: Bool = try Bool(derEncoded: &nodes) let f: Bool = try Bool(derEncoded: &nodes) let g: [ArraySlice<UInt8>]? = try DER.set(of: ArraySlice<UInt8>.self, identifier: .set, nodes: &nodes) let h: ArraySlice<UInt8> = try ArraySlice<UInt8>(derEncoded: &nodes) let i: ArraySlice<UInt8> = try ArraySlice<UInt8>(derEncoded: &nodes) let j: ASN1OctetString? = try ASN1OctetString(derEncoded: &nodes) let k: Bool? = try Bool(derEncoded: &nodes) return V2(a: a, b: b, c: c, d: d, e: e, f: f, g: g, h: h, i: i, j: j, k: k) } } @inlinable func serialize(into coder: inout DER.Serializer, withIdentifier identifier: ASN1Identifier) throws { try coder.appendConstructedNode(identifier: identifier) { coder in try coder.serializeSetOf(a) try coder.serializeSetOf(b) try coder.serialize(c) try coder.serialize(d) try coder.serialize(e) try coder.serialize(f) if let g = self.g { try coder.serializeSetOf(g) } try coder.serialize(h) try coder.serialize(i) if let j = self.j { try coder.serialize(j) } if let k = self.k { try coder.serialize(k) } } } }

Рекурсивні суми та їх теги

Перше шо ви повинні зробити перед тим як публікувати ASN.1 компілятор на сайті ITU.INT це пересвідчитися шо він сприймає класичне визначення рекурсивного списку з книжки Олівʼє Дебюсона [6].

List ::= SEQUENCE { data OCTET STRING, next CHOICE { linked-list List, end NULL } }
@usableFromInline struct List: DERImplicitlyTaggable, Hashable, Sendable { @inlinable static var defaultIdentifier: ASN1Identifier { .sequence } @usableFromInline var data: ASN1OctetString @usableFromInline var next: List_next_Choice @inlinable init(data: ASN1OctetString, next: List_next_Choice) { self.data = data ; self.next = next } @inlinable init(derEncoded root: ASN1Node, withIdentifier identifier: ASN1Identifier) throws { self = try DER.sequence(root, identifier: identifier) { nodes in let data: ASN1OctetString = try ASN1OctetString(derEncoded: &nodes) let next: List_next_Choice = try List_next_Choice(derEncoded: &nodes) return List(data: data, next: next) } } @inlinable func serialize(into coder: inout DER.Serializer, withIdentifier identifier: ASN1Identifier) throws { try coder.appendConstructedNode(identifier: identifier) { coder in try coder.serialize(data) try coder.serialize(next) } } } @usableFromInline indirect enum List_next_Choice: DERParseable, DERSerializable, Hashable, Sendable { case linked_list(List) case end(ASN1Null) @inlinable init(derEncoded rootNode: ASN1Node) throws { switch rootNode.identifier { case List.defaultIdentifier: self = .linked_list(try List(derEncoded: rootNode)) case ASN1Null.defaultIdentifier: self = .end(try ASN1Null(derEncoded: rootNode)) default: throw ASN1Error.unexpectedFieldType(rootNode.identifier) } } @inlinable func serialize(into coder: inout DER.Serializer) throws { switch self { case .linked_list(let linked_list): try coder.serialize(linked_list) case .end(let end): try coder.serialize(end) } } }

Якщо ви хочете тримати в сумі різні значення однакового типу ви повинні використовувати врапери теги, які бувають двох видів: 1) імплісіти (129) і 2) експлісіти (160).

A ::= CHOICE { v [0] V, list-x [1] List, o [2] SET OF OCTET STRING, s [3] SET OF OCTET STRING, }
@usableFromInline indirect enum A: DERParseable, DERSerializable, Hashable, Sendable { case v(V) case list_x(List) case o([ASN1OctetString]) case s([ASN1OctetString]) @inlinable init(derEncoded rootNode: ASN1Node) throws { switch rootNode.identifier { case ASN1Identifier(tagWithNumber: 0, tagClass: .contextSpecific): self = .v(try V(derEncoded: rootNode)) case ASN1Identifier(tagWithNumber: 1, tagClass: .contextSpecific): self = .list_x(try List(derEncoded: rootNode)) case ASN1Identifier(tagWithNumber: 2, tagClass: .contextSpecific): self = .o(try DER.set(of: ASN1OctetString.self, identifier: .set, rootNode: rootNode)) case ASN1Identifier(tagWithNumber: 3, tagClass: .contextSpecific): self = .s(try DER.sequence(of: ASN1OctetString.self, identifier: .sequence, rootNode: rootNode)) default: throw ASN1Error.unexpectedFieldType(rootNode.identifier) } } @inlinable func serialize(into coder: inout DER.Serializer) throws { switch self { case .v(let v): try coder.appendConstructedNode( identifier: ASN1Identifier(tagWithNumber: 0, tagClass: .contextSpecific), { coder in try coder.serialize(v) }) case .list_x(let list_x): try coder.appendConstructedNode( identifier: ASN1Identifier(tagWithNumber: 1, tagClass: .contextSpecific), { coder in try coder.serialize(list_x) }) case .o(let o): try coder.appendConstructedNode( identifier: ASN1Identifier(tagWithNumber: 2, tagClass: .contextSpecific), { coder in try coder.serializeSetOf(o) }) case .s(let s): try coder.appendConstructedNode( identifier: ASN1Identifier(tagWithNumber: 3, tagClass: .contextSpecific), { coder in try coder.serializeSequenceOf(s) }) } } }

Імплісіти, експлісіти та опшинали

Якщо ви хочете позначити поле додатковою інформацією такою як можливіть приймати значення NULL (OPTIONAL) та вид тегування (129, 160).

V ::= SEQUENCE { a [1] IMPLICIT SET OF INTEGER (0..7), b [2] EXPLICIT SET OF INTEGER (0..7), c [3] IMPLICIT INTEGER (0..7), d [4] EXPLICIT INTEGER (0..7), e [5] IMPLICIT BOOLEAN, f [6] EXPLICIT BOOLEAN, g [7] IMPLICIT SET OF INTEGER (0..7) OPTIONAL, h [8] EXPLICIT SET OF INTEGER (0..7) OPTIONAL, i [9] IMPLICIT INTEGER (0..7) OPTIONAL, j [0] EXPLICIT INTEGER (0..7) OPTIONAL, k OCTET STRING OPTIONAL, l BOOLEAN OPTIONAL }
@usableFromInline struct V: DERImplicitlyTaggable, Hashable, Sendable { @inlinable static var defaultIdentifier: ASN1Identifier { .sequence } @usableFromInline var a: [ArraySlice<UInt8>] @usableFromInline var b: [ArraySlice<UInt8>] @usableFromInline var c: ArraySlice<UInt8> @usableFromInline var d: ArraySlice<UInt8> @usableFromInline var e: Bool @usableFromInline var f: Bool @usableFromInline var g: [ArraySlice<UInt8>]? @usableFromInline var h: [ArraySlice<UInt8>]? @usableFromInline var i: ArraySlice<UInt8>? @usableFromInline var j: ArraySlice<UInt8>? @usableFromInline var k: ASN1OctetString? @usableFromInline var l: Bool? @inlinable init(a: [ArraySlice<UInt8>], b: [ArraySlice<UInt8>], c: ArraySlice<UInt8>, d: ArraySlice<UInt8>, e: Bool, f: Bool, g: [ArraySlice<UInt8>]?, h: [ArraySlice<UInt8>]?, i: ArraySlice<UInt8>?, j: ArraySlice<UInt8>?, k: ASN1OctetString?, l: Bool?) { self.a = a ; self.b = b ; self.c = c ; self.d = d ; self.e = e ; self.f = f ; self.g = g ; self.h = h ; self.i = i ; self.j = j ; self.k = k ; self.l = l } @inlinable init(derEncoded root: ASN1Node, withIdentifier identifier: ASN1Identifier) throws { self = try DER.sequence(root, identifier: identifier) { nodes in let a: [ArraySlice<UInt8>] = try DER.set(of: ArraySlice<UInt8>.self, identifier: ASN1Identifier(tagWithNumber: 1, tagClass: .contextSpecific), nodes: &nodes) let b: [ArraySlice<UInt8>] = try DER.explicitlyTagged(&nodes, tagNumber: 2, tagClass: .contextSpecific) { node in try DER.set(of: ArraySlice<UInt8>.self, identifier: .set, rootNode: node) } let c: ArraySlice<UInt8> = (try DER.optionalImplicitlyTagged(&nodes, tag: ASN1Identifier(tagWithNumber: 3, tagClass: .contextSpecific)))! let d: ArraySlice<UInt8> = try DER.explicitlyTagged(&nodes, tagNumber: 4, tagClass: .contextSpecific) { node in return try ArraySlice<UInt8>(derEncoded: node) } let e: Bool = (try DER.optionalImplicitlyTagged(&nodes, tag: ASN1Identifier(tagWithNumber: 5, tagClass: .contextSpecific)))! let f: Bool = try DER.explicitlyTagged(&nodes, tagNumber: 6, tagClass: .contextSpecific) { node in return try Bool(derEncoded: node) } let g: [ArraySlice<UInt8>] = try DER.set(of: ArraySlice<UInt8>.self, identifier: ASN1Identifier(tagWithNumber: 7, tagClass: .contextSpecific), nodes: &nodes) let h: [ArraySlice<UInt8>]? = try DER.optionalExplicitlyTagged(&nodes, tagNumber: 8, tagClass: .contextSpecific) { node in try DER.set(of: ArraySlice<UInt8>.self, identifier: .set, rootNode: node) } let i: ArraySlice<UInt8>? = try DER.optionalImplicitlyTagged(&nodes, tag: ASN1Identifier(tagWithNumber: 9, tagClass: .contextSpecific)) let j: ArraySlice<UInt8>? = try DER.optionalExplicitlyTagged(&nodes, tagNumber: 0, tagClass: .contextSpecific) { node in return try ArraySlice<UInt8>(derEncoded: node) } let k: ASN1OctetString? = try ASN1OctetString(derEncoded: &nodes) let l: Bool? = try Bool(derEncoded: &nodes) return V(a: a, b: b, c: c, d: d, e: e, f: f, g: g, h: h, i: i, j: j, k: k, l: l) } } @inlinable func serialize(into coder: inout DER.Serializer, withIdentifier identifier: ASN1Identifier) throws { try coder.appendConstructedNode(identifier: identifier) { coder in try coder.serializeSetOf(a, identifier: ASN1Identifier(tagWithNumber: 1, tagClass: .contextSpecific)) try coder.serialize(explicitlyTaggedWithTagNumber: 2, tagClass: .contextSpecific) { codec in try codec.serializeSetOf(b) } try coder.serializeOptionalImplicitlyTagged(c, withIdentifier: ASN1Identifier(tagWithNumber: 3, tagClass: .contextSpecific)) try coder.serialize(explicitlyTaggedWithTagNumber: 4, tagClass: .contextSpecific) { codec in try codec.serialize(d) } try coder.serializeOptionalImplicitlyTagged(e, withIdentifier: ASN1Identifier(tagWithNumber: 5, tagClass: .contextSpecific)) try coder.serialize(explicitlyTaggedWithTagNumber: 6, tagClass: .contextSpecific) { codec in try codec.serialize(f) } if let g = self.g { try coder.serializeSetOf(g, identifier: ASN1Identifier(tagWithNumber: 7, tagClass: .contextSpecific)) } if let h = self.h { try coder.serialize(explicitlyTaggedWithTagNumber: 8, tagClass: .contextSpecific) { codec in try codec.serializeSetOf(h) } } if let i = self.i { try coder.serializeOptionalImplicitlyTagged(i, withIdentifier: ASN1Identifier(tagWithNumber: 9, tagClass: .contextSpecific)) } if let j = self.j { try coder.serialize(explicitlyTaggedWithTagNumber: 0, tagClass: .contextSpecific) { codec in try codec.serialize(j) } } if let k = self.k { try coder.serialize(k) } if let l = self.l { try coder.serialize(l) } } } }

Переліки та цілочисельні переліки

Versioning ::= INTEGER { v1(0) }
public struct Versioning : Hashable, Sendable, Comparable { @usableFromInline var rawValue: Int @inlinable public static func < (lhs: Versioning, rhs: Versioning) -> Bool { lhs.rawValue < rhs.rawValue } @inlinable init(rawValue: Int) { self.rawValue = rawValue } public static let v1 = Self(rawValue: 0) }
CountryName ::= [APPLICATION 1] CHOICE { x121-dcc-code NumericString (SIZE (ub-country-name-numeric-length)), iso-3166-alpha2-code PrintableString (SIZE (ub-country-name-alpha-length)) }
@usableFromInline indirect enum CountryName: DERParseable, DERSerializable, Hashable, Sendable { case x121_dcc_code(ASN1PrintableString) case iso_3166_alpha2_code(ASN1PrintableString) @inlinable init(derEncoded rootNode: ASN1Node) throws { switch rootNode.identifier { case ASN1PrintableString.defaultIdentifier: self = .x121_dcc_code(try ASN1PrintableString(derEncoded: rootNode)) case ASN1PrintableString.defaultIdentifier: self = .iso_3166_alpha2_code(try ASN1PrintableString(derEncoded: rootNode)) default: throw ASN1Error.unexpectedFieldType(rootNode.identifier) } } @inlinable func serialize(into coder: inout DER.Serializer) throws { switch self { case .x121_dcc_code(let x121_dcc_code): try coder.serialize(x121_dcc_code) case .iso_3166_alpha2_code(let iso_3166_alpha2_code): try coder.serialize(iso_3166_alpha2_code) } } }

Тензори

K ::= SEQUENCE { w SET OF SEQUENCE OF SET OF SEQUENCE OF INTEGER }
@usableFromInline struct K: DERImplicitlyTaggable, Hashable, Sendable { @inlinable static var defaultIdentifier: ASN1Identifier { .sequence } @usableFromInline var w: [[[[ArraySlice<UInt8>]]]] @inlinable init(version: K_version_IntEnum, x: ArraySlice<UInt8>, y: K_y_Sequence, w: [[[[ArraySlice<UInt8>]]]]) { self.w = w } @inlinable init(derEncoded root: ASN1Node, withIdentifier identifier: ASN1Identifier) throws { self = try DER.sequence(root, identifier: identifier) { nodes in let w: [[[[ArraySlice<UInt8>]]]] = try DER.set<[[[[ArraySlice<UInt8>]]]]>(nodes.next()!, identifier: .set) { nodes1 in var wAcc1: [[[[ArraySlice<UInt8>]]]] = [] while let wInner1 = nodes1.next() { wAcc1.append( try DER.sequence<[[[ArraySlice<UInt8>]]]>(wInner1, identifier: .sequence) { nodes2 in var wAcc2: [[[ArraySlice<UInt8>]]] = [] while let wInner2 = nodes2.next() { wAcc2.append( try DER.set<[[ArraySlice<UInt8>]]>(wInner2, identifier: .set) { nodes3 in var wAcc3: [[ArraySlice<UInt8>]] = [] while let wInner3 = nodes3.next() { wAcc3.append( try DER.sequence(of: ArraySlice<UInt8>.self, identifier: .sequence, rootNode: wInner3) )} return wAcc3 } )} return wAcc2 } )} return wAcc1 } return K(version: version, x: x, y: y, w: w) } } @inlinable func serialize(into coder: inout DER.Serializer, withIdentifier identifier: ASN1Identifier) throws { try coder.appendConstructedNode(identifier: identifier) { coder in try coder.appendConstructedNode(identifier: .set) { codec1 in for element1 in w { try codec1.appendConstructedNode(identifier: .sequence) { codec2 in for element2 in element1 { try codec2.appendConstructedNode(identifier: .set) { codec3 in for element3 in element2 { try codec3.serializeSequenceOf(element3) } } } } } } } } }

Висновок

Найкращий спосіб вивчити ASN.1 — це написати ASN.1 компілятор. Був детально проаналізований X.680 стандарт та знайдені конкуретні переваги над іншими компіляторами: 1) більшість не підтримують рекурсивні типи даних, 2) більшість не підримують повністю всі ASN.1 файли ITU.INT, 3) більшість не підтримують тензори. Наш компілятор зроблений таким, що усуває ці недоліки. Що стосується швидкості парсерів Apple для мови Swift, то вони в середньому в два рази повільніші за fast_ber парсерів на C++ і в 2 рази швидші за парсери asn1c.

Реалізація використовує потоковий бінарний парсер ASN.1 файлів на 2000 рядків коду разом з токенайзером, що йдуть в дистрибутиві Erlang/OTP в аплікейшині asn1, а сам компілятор виконаний як script файл для мови Elixir на 600 рядків і не потребує компіляції. Найближчі конкуренти asn1c і asn1іcc займають 25000 рядків.

Доведення коректності компілятора має комбінаторний вигляд, а головна теорема стверджує шо за 2 проходи, можна повністю скомпілювати ASN.1 X.680 стандарт в будь яку мову програмування, кожен прохід містить доведення коректності 11 циклів, разом які використовують 50 розгалужень кожне з яких доводиться окремо в комбінаторному стилі кейс аналізом. За перший прохід будують часткові форвард декларації, які повністю стають насиченими на другому проході. В процесі першого проходу не зберігаються файли, зате між проходами не очищується контекст, який містить три типи ключів: визначення типів для носіння полів та їх властивостей, синоніми, та специфікатори тензорів. Також компілятор містить verbose опцію -v яка показує всі стадії насичення контексту.

На розробку компілятора був витрачений 1 людино-місяць та згенеровано ним 30000 рядків Swift 5.8 коду який працює на Windows/Linux/Mac. Цей код покриває всі конверти які можна знайти на сайті ITU.INT у вигляді ASN.1 файлів. Сюди входять PKIX, CMP, CMC, LDAP, CMS, PKCS, X.400, тощо. Компілятор asn1scc написаний на F# який підтримується Європейським Космічним Агенством не працює на повній множині всіх цих декларацій, а займає теж немало, 32000 рядків на F#.

$ brew install elixir $ git clone [email protected]:erpuno/asn1 $ ./asn1.ex compile -v priv/apple Sources/ASN1SCG $ swift build

˙

˙

[1]. ITU-T ASN.1 Compilers
[2]. Apple Swift ASN.1 Library Documentation.
[3]. Let's Encrypt. Ласкаво просимо в ASN.1 і DER
[4]. Swift Crypto Library Documentation
[5]. Swift Certificates Library Documentation
[6]. Olivier Dubuisson. ASN.1 Communication between Heterogeneous Systems